package com.sise.Stack;

import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

/**
 *      347. 前 K 个高频元素
 *
 *      给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
 *      输入: nums = [1,1,1,2,2,3], k = 2
 *      输出: [1,2]
 */
public class _hot_347_topKFrequent {

    public int[] topKFrequent(int[] nums, int k) {

        Map<Integer, Integer> occurrences = new HashMap<>();        // 数字作为 key，数字出现的次数作为 value。
        for (int num : nums) {
            occurrences.put(num, occurrences.getOrDefault(num, 0) + 1);     // getOrDefault() 如果不存在这个 key，那么就返回 Map<key:0>，存在则在原有基础上加一
        }

        PriorityQueue<int[]> queue = new PriorityQueue<int[]>(new Comparator<int[]>() {     // 小根堆，将最小值放在最上面，如果比顶部节点小，那么就直接排除
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[1] - o2[1];                                                       // 这里比较的是数组 int[]{key,value}，而不是 Map。故此通过 int[1] 得到 value
            }
        });

        for (Map.Entry<Integer, Integer> entry : occurrences.entrySet()){
            int num = entry.getKey();
            int count = entry.getValue();
            if (queue.size() == k){                     // 如果最小堆的长度与 k 相等，那么就需要判断当前元素 与 堆顶元素的大小
                if (queue.peek()[1] < count){           // 如果当前的数值 count 大于 堆顶元素int[1]，那么就选择替换
                    queue.poll();                       // 删除堆顶元素
                    queue.offer(new int[]{num, count}); // 向最小堆中插入元素 int[]{key,value}
                }
            }else {
                queue.offer(new int[]{num, count});     // 堆中还未满，故此直接往最小堆中插入数据
            }
        }

        int[] res = new int[k];
        for (int i = 0; i < k; i++){                    // 将目前最小堆中的数据插入到 结果集，这里插入的是 key
            res[i] = queue.poll()[0];
        }
        return res;
    }
}
